package test;

import java.util.ArrayList;
import java.util.List;

//电话号码的字母组合：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
//时间复杂度：O(k^n),k由所有String的最大长度决定，本题k=4
public class LetterCombinations {
	public List<String> ret;
    public StringBuilder path;
    public void dfs(String[] nums,int pos){
        if(nums.length==path.length()){
            ret.add(new String(path.toString()));
            return ;
        }
        for(int i=0;i<nums[pos].length();i++){
        	//本题是一定要选
            char c=nums[pos].charAt(i);
            path.append(c);
            dfs(nums,pos+1);
            path.deleteCharAt(path.length()-1);
        }  
    }
    //nums: 数字映射的字符串
    public List<String> letterCombinations(String digits) {
        String[] str=new String[]{null,null,"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        ret=new ArrayList<>();
        path=new StringBuilder();
        if(digits.length()==0) return ret;
        String[] s=new String[digits.length()];
        //映射digits数组
        for(int i=0;i<digits.length();i++){
            int index=digits.charAt(i)-'0';
            s[i]=str[index];
        }
        dfs(s,0);
        return ret;
    }
}
